package main

import (
	"fmt"
	"math"
)

func main() {
	n := 268341
	fmt.Println(reorderedPowerOf2(n))
}

//#link: https://leetcode-cn.com/problems/reordered-power-of-2/
func reorderedPowerOf2(n int) (ans bool) {
	//1. 将整数进行拆分
	nums := make([]int, 0)
	for n > 0 {
		nums = append(nums, n%10)
		n /= 10
	}
	var backTrace func([]int, []int)
	//2. 拆分后的数组进行全排列,同时判断是否为2的幂
	backTrace = func(nums, path []int) {
		if len(path) == len(nums) {
			// 3.将数组转换为整数
			targetNum := 0
			for i := 0; i < len(path); i++ {
				if targetNum == 0 && path[i] == 0 {
					continue
				}
				targetNum += int(math.Pow(10, float64(i))) * path[len(path)-i-1]
			}
			log2 := math.Log2(float64(targetNum))
			if 1<<uint32(log2) == targetNum {
				//fmt.Println(targetNum,log2)
				ans = true
			}
			return
		}
		for i := 0; i < len(nums); i++ {
			path = append(path, nums[i])
			backTrace(nums, path)
			path = path[:len(path)-1]
		}
	}

	backTrace(nums, []int{})
	return ans
}
